



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 16, Exercise 3<BR>

<BR>

</H1>



Define a directed graph with as many vertices as the number

of

balls on Mary's side of the court plus 1.  One of these vertices

represents the location of the basket and each of the remaining vertices 

represents the location of a ball.

The digraph is a complete digraph and the length of the edge

<em class=var>(i,j)</em> is the distance between

the locations represented by the vertices <em class=var>i</em>

and <em class=var>j</em>.

The solution to the traveling salesperson problem defined on this digraph

gives us the shortest route Mary can take to pick up the balls on her

side of the court.

<br><br>

For Joe's side of the court, we can define an analogous traveling

salesperson problem.  So by solving two traveling salesperson

problems, we can find the order in which Mary and Joe should pick

up balls so that they walk the minimum distance.



</FONT>

</BODY>

</HTML>

